package leetcode_day._2022._202204;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/4 23:53
 * 区域和检索 - 数组可修改
 * 算法：树状数组
 * y = lowbit(x)
 * 比如：4, y = 4, S4 = n1 + n2 + n3 + n4; 5, y = 1, S5 = n5
 */
public class _04_307 {
    class NumArray {
        int[] sum, nums;

        public NumArray(int[] nums) {
            // 下标从 1 开始，因为 0 会死循环
            this.sum = new int[nums.length + 1];
            this.nums = nums;
            for (int i = 0; i < nums.length; i++) insert(i, nums[i]);
        }

        /**
         * idx 只会影响 sum[idx] 及其后面的数
         */
        public void update(int idx, int val) {
            int x = idx + 1;
            while (x < sum.length) {
                sum[x] = sum[x] - nums[idx] + val;
                x += lowbit(x);
            }
            nums[idx] = val;
        }

        public int sumRange(int left, int right) {
            return query(right + 1) - query(left);
        }

        int lowbit(int x) {
            return x & (-x);
        }

        /**
         * 插入数字，初始化
         */
        void insert(int idx, int val) {
            int x = idx + 1;
            while (x < sum.length) {
                sum[x] += val;
                x += lowbit(x);
            }
        }

        int query(int x) {
            int res = 0;
            while (x != 0) {
                res += sum[x];
                x -= lowbit(x);
            }
            return res;
        }

    }
}
